#define _CRT_RAND_S
#include <pthread.h>
#include <malloc.h>
#include <stdio.h>
#include <stdlib.h>
#include <ctime>
#include <time.h>

struct args_t {
	int thread_number;
	void* data;
	int begin;
	int end;
};

struct data_t {
	int *array;
	bool is_first;
	FILE** fps;
};

void parallel_for(void*(*f)(void*), void* data, int begin, int end, int grainsize, int n_threads)
{
	pthread_t* threads;
	struct args_t* args;

	threads = (pthread_t*) malloc(sizeof(pthread_t) * n_threads);
	args = (struct args_t*) malloc(sizeof(struct args_t) * n_threads);

	for (int i = begin; i < end; i += grainsize * n_threads)
	{
		for (int j = 0; j < n_threads; j++)
		{
			args[j].data = data;
			args[j].begin = i + j * grainsize;
			args[j].end = i + (j + 1) * grainsize;
			args[j].thread_number = j;

			if (args[j].begin < end)
			{
				if (args[j].end >= end)
					args[j].end = end;
				pthread_create(threads + j, NULL, f, (void*)(args + j));
			}
		}

		for (int j = 0; j < n_threads; j++)
			pthread_join(*(threads + j), NULL);
	}

	free(args);
	free(threads);
}

void* sort_from_file(void* _arg)
{
	struct args_t* arg = (struct args_t*)_arg;
	data_t* data = (data_t*)arg->data;
	int* array = (int*)malloc(sizeof(int) * (arg->end - arg->begin));
	FILE *fp = data->fps[arg->thread_number];
	int begin = arg->begin;

	fseek(fp, sizeof(int)*begin, SEEK_SET);
	fread(array, sizeof(int), arg->end - arg->begin, fp);
	arg->end = (arg->end - arg->begin);
	arg->begin = 0;
	for (int i = arg->begin; i < arg->end - 1; i++)
		for (int j =  data->is_first || i >= (arg->begin+arg->end)/2?i+1:(arg->begin+arg->end)/2; j < arg->end; j++)
		{
			if (array[j] < array[i])
			{
				int tmp = array[j];
				array[j] = array[i];
				array[i] = tmp;
			}
		}
	fseek(fp, sizeof(int)*begin, SEEK_SET);
	fwrite(array, sizeof(int), arg->end, fp);
	free(array);
	return NULL;
}

pthread_mutex_t rand_mutex = PTHREAD_MUTEX_INITIALIZER;

void* fill_rand(void* _arg)
{  
	struct args_t* arg = (struct args_t*)_arg;
	int* data = (int*)arg->data;
	for (int i = arg->begin; i < arg->end; i++)
	{
		pthread_mutex_lock(&rand_mutex);
		rand_s((unsigned int*)data + i);
		data[i] = (unsigned int)data[i] % 1000;
		pthread_mutex_unlock(&rand_mutex);
	}
	return NULL;
}

int main()
{
	int max_memory = 1024*1024; //in bytes
	const int n_threads = 4;
	const int N = 1024*1024;
	int grainsize = N > max_memory / sizeof(int) ? max_memory / sizeof(int) / n_threads : N / n_threads;
	int* data_array = (int*)malloc(sizeof(int) * N);
	clock_t time_begin;
	clock_t time_end;
	FILE **fps = (FILE**)malloc(sizeof(FILE*) * n_threads);
	srand(time(NULL));

	/********* Fill array ***********/
	printf("grainsize=%d\n", grainsize);
	printf("Creating a random sequence...");
	parallel_for(&fill_rand, (void*)data_array, 0, N, grainsize, n_threads);
	printf("\rCreating a random sequence...      OK\n");

	/********* Save to file ***********/
	printf("Data storage...");
	FILE *fp = fopen("data.bin", "wb+");
	fwrite(data_array, sizeof(int), N, fp);
	fclose(fp);
	free(data_array);
	printf("\rData storage...                    OK\n");

	/********* Sort file ***********/
	for (int i = 0; i < n_threads; i++)
		fps[i] = fopen("data.bin", "rb+");
	time_begin=clock();
	for (int i = 0; i < (N / grainsize + (N % grainsize != 0)) * 2; i++)
	{
		struct data_t data = {data_array, !i, fps};
		float persent = (float)i / ((N / grainsize + (N % grainsize != 0)) * 2)*100;
		float elapsed_time = float(clock() - time_begin) / CLOCKS_PER_SEC;
		printf("\rData sorting...                    %.2f%% completed   Time left ~%.2f sec  ", persent, elapsed_time / (persent!=0?persent:1000000000) * 100 - elapsed_time);
		parallel_for(&sort_from_file, (void*)&data, 0 + i%2==0?0:grainsize/2, N, grainsize, n_threads);
	}
	time_end=clock();
	for (int i = 0; i < n_threads; i++)
		fclose(fps[i]);
	printf("\rData sorting...                    100%% completed                             \n");

	/********* Vilidation of sorting ***********/
	printf("Validation of sorting...");
	data_array = (int*)malloc(sizeof(int) * N);
	fp = fopen("data.bin", "rb");
	fread(data_array, sizeof(int), N, fp);
	for (int i = 1; i < N; i++)
		if (data_array[i] < data_array[i - 1])
			printf("\nerror %d %d\n", i - 1, i);
	fclose(fp);
	free(data_array);
	printf("\rValidation of sorting...           OK\n");


	printf("Time spent for sorting             %.2f sec\n", float(time_end - time_begin) / CLOCKS_PER_SEC);
}















/*********************** from memory ***********************/
void* sort(void* _arg)
{
	struct args_t* arg = (struct args_t*)_arg;
	data_t* data = (data_t*)arg->data;
	bool is_first = data->is_first;
	int* array = data->array;
	//printf("from %d %d\n", arg->start, arg->stop);
	for (int i = arg->begin; i < arg->end - 1; i++)
		for (int j = is_first || i >= (arg->begin+arg->end)/2?i+1:(arg->begin+arg->end)/2; j < arg->end; j++)
		{
			if (array[j] < array[i])
			{
				int tmp = array[j];
				array[j] = array[i];
				array[i] = tmp;
			}
		}
		return NULL;
}

int main1()
{
	const int n_threads = 4;
	const int N = 100;
	int grainsize = N / n_threads;

	int* data_array = (int*)malloc(sizeof(int) * N);
	clock_t time_begin;
	clock_t time_end;
	float ratio;

	if (data_array == NULL)
	{
		puts("Can't malloc!!!!!!!!!");
		exit(1);
	}
	srand(time(NULL));

	/*********  Linear  *********/
	parallel_for(&fill_rand, (void*)data_array, 0, N, grainsize, n_threads);
	time_begin=clock();
	struct data_t data = {data_array, true};
	struct args_t arg = { 0, &data, 0, N};
	sort((void*)&arg);
	time_end=clock();
	ratio = double(time_end - time_begin) / CLOCKS_PER_SEC;
	printf("linear: elapsed time %g sec\n", double(time_end - time_begin) / CLOCKS_PER_SEC);

	/********  Parallel  ********/
	parallel_for(&fill_rand, (void*)data_array, 0, N, grainsize, n_threads);
	time_begin=clock();
	for (int i = 0; i < (N / grainsize + (N % grainsize != 0)) * 2; i++)
	{
		struct data_t data = {data_array, !i};
		parallel_for(&sort, (void*)&data, 0 + i%2==0?0:grainsize/2, N, grainsize, n_threads);
	}
	time_end=clock();

	/*******  Output  ***********/
	printf("parallel: elapsed time %g sec\n", double(time_end - time_begin) / CLOCKS_PER_SEC);
	printf("ratio=%g\n\n", ratio / (double(time_end - time_begin) / CLOCKS_PER_SEC));
	for (int i = 0; i < N; i++)
		printf("%d ", data_array[i]);
	for (int i = 1; i < N; i++)
		if (data_array[i] < data_array[i - 1])
			printf("error %d %d\n", i - 1, i);
	return 0;
}